This invention relates to a method of, and system for, propagating a query in a network of connected nodes. In one embodiment, the invention provides a method to dynamically route information through the fastest most trusted path in a network.
A federated database is made up of a number of interconnected database management systems (DBMSs), each of which manages one or more databases. The federated database allows a single query to access the databases through the interconnected DBMSs. In one known method of propagating a query in a federated database, the query is received by the federated database and propagated over connections between the various DBMSs. DBMSs that control databases targeted by the query then translate the query into actions that are compatible with the databases they control. As the size of a database federation increases, various scaling problems can occur. For example, as new DBMSs are added to the federated database, the number of connections between the DBMSs may increase in a combinatorial fashion. This can lead to an unwieldy number of connections in a federated database that contains only a moderate number of DBMSs. Further, the network topology of the federated database may also lead to data that is inaccessible following the failure of a connection or DBMS. Additionally, when a query is made to the database federation, the communication overhead in distributing the query to all of the DBMSs can be significant. Various methods of propagating queries are known in the prior art.
In the operation of a Dynamic Distributed Federated Database (DDFD), where distributed data sources are federated across a network of inter-connected self-organizing DDFD nodes, it may be that, in such networks, the route selected to propagate a query is not the best, for other reasons. For example, the data sources and DDFD nodes may be owned by different organizations some of which may be trusted (in some sense) while others may be non-trusted. The routing of queries and their replies through non-trusted nodes is a significant problem in that there is a desire to find the quickest route between nodes, but data must ideally not travel through non-trusted nodes.
In static networks, which are not changing rapidly, a trivial solution to this problem is to centrally determine the structure of the network and to compute the path(s) that minimize the distance between the querying node and the data source(s) via the minimum number of non-trusted nodes. A node from which a query is to be launched could query this central system, asking if the data can be sent through a certain path. This central system can hold policy for all of the nodes and their interaction. This approach is not appropriate in the case of a DDFD, due to the dynamic and self-organizing nature of such systems, which means that there is no central system that maintains information about the network topology.